package demo;

/**
 * 快速排序
 */
class Solution5 {
	public int[] sortArray(int[] nums) {
		quickSort(nums, 0, nums.length - 1);
		return nums;
	}

	public void quickSort(int[] arr,int l,int r){
		if (l >= r) {
			return;
		}
		if(l<r){ //跳出递归的条件
			//partition就是划分操作，将arr划分成满足条件的两个子表
			int pivotpos = partition(arr,l,r);
			//依次对左右两个子表进行递归排序
			quickSort(arr,l,pivotpos-1);
			quickSort(arr,pivotpos+1,r);
		}
	}

	public int partition(int[] arr,int l,int r){
		//以当前数组的最后一个元素作为中枢pivot，进行划分
		int pivot = arr[r];
		while (l<r){
			while (l<r && arr[l]<pivot) {
				l++;
			}
			arr[r] = arr[l];
			//将比中枢值大的移动到右端r处 由于r处为中枢或者该位置值已经被替换到l处，所以直接可以替换
			while (l<r && arr[r]>=pivot){
				r--;
			}
			arr[l] = arr[r];//将比中枢值小的移动到左端l处 由于前面l处的值已经换到r处，所以该位置值也可以替换掉
		}
		//l==r时，重合，这个位置就是中枢的最终位置
		arr[l] = pivot;
		//返回存放中枢的最终位置
		return l;
	}

	public static void main(String[] args) {
		int[] nums = new int []{2,3,1,7,9,5,6};
		new Solution5().sortArray(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.println(nums[i]);
		}
	}
}

